package _20_十大排序算法;


import java.util.Arrays;

// 初始化双指针，并且最左边的指针为轴点元素
// 向遍历右边，如果右边大于轴点元素，右指向左移动，
// 如果小鱼轴点元素，那就和轴点元素交换位置，并且指针向左移动
// 并且在快速排序的过程中，也是不断分割子序列，递归对轴点左右两边的数据再次进行快速排序
public class _05_快速排序 {

    public static void main(String[] args) {

        _05_快速排序 v = new _05_快速排序();
        int[] ins = new int[]{6, 8, 2, 8, 6, 4, 9, 5, 7};

        v.quickSort(ins);

        System.out.println(Arrays.toString(ins));
    }

    public void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length);
    }

    public void quickSort(int[] nums, int begin, int end) {
        if (end - begin < 2) return;
        // 返回轴点元素，所在位置
        int mid = pivotIndex(nums, begin, end);
        // 递归对轴点左右进行快速排序
        quickSort(nums, begin, mid);
        quickSort(nums, mid + 1, end);
    }

    // 将所有元素和轴点元素比较，直接比较的都是和轴点元素
    // 大于的放右边，小于的放左边，最终就可以产生在轴点左边偏序，和在轴点右边偏序
    // 如果依据现在的算法，把比较改成等于，那么分割出来的序列会极度不均匀，导致出现n^2的复杂度
    private int pivotIndex(int[] nums, int begin, int end) {
        int pivot = nums[begin];
        end--;
        while (begin < end) {
            while (begin < end) {
                if (nums[end] > pivot) end--;
                else {
                    // 和begin元素交换
                    nums[begin++] = nums[end];
                    break;
                }
            }
            while (begin < end) {
                if (nums[begin] < pivot) begin++;
                else {
                    // 和begin元素交换
                    nums[end--] = nums[begin];
                    break;
                }
            }
        }
        nums[begin] = pivot;
        return begin;
    }

}
